# -*- coding: utf-8 -*-
"""
    Time    : 2021/1/1 6:06 下午
    Author  : Thinkgamer
    File    : add09-从一个带权重的数组中随机选取k个数.py
    Desc    : 探探面试 / 百度面试
            eg： {"a": 2, "b": 3, "c": 3, "d": 2}
"""
import random


def random_select_k(arr, k):
	new_arr_weight = [("a", 0, 2)]
	for i in range(1, len(arr)):
		new_arr_weight.append((arr[i][0], new_arr_weight[i-1][2], new_arr_weight[i-1][2] + arr[i][1]))
	print(new_arr_weight)
	
	result = list()
	while k > 0:
		v = random.randint(0, new_arr_weight[-1][2])
		print(v)
		for (w, start, end) in new_arr_weight:
			if start <= v < end:
				result.append(w)
				break
		k -= 1
	return result


arr_weight = [("a", 2), ("b", 3), ("c", 3), ("d", 2)]
k = 2
result = random_select_k(arr_weight, k)
print(result)
